package leetcode.editor.cn;

import java.util.Comparator;
import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class _239_SlidingWindowMaximum {
    public static void main(String[] args) {
        Solution solution = new _239_SlidingWindowMaximum().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // 大顶堆 PriorityQueue
    class Solution1 {
        public int[] maxSlidingWindow(int[] nums, int k) {
            int n = nums.length;
            // 初始化大顶堆
            PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o2[0] - o1[0];
                }
            });
            for (int i = 0; i < k; i++) {
                pq.add(new int[]{nums[i], i});
            }
            int[] res = new int[n - k + 1];
            res[0] = pq.peek()[0];
            for (int i = k; i < n; i++) {
                pq.add(new int[]{nums[i], i});
                // 这一步是关键 : 保证堆顶在窗口内
                while (pq.peek()[1] <= i - k) {
                    pq.remove();
                }
                res[i - k + 1] = pq.peek()[0];
            }
            return res;
        }
    }

    // 单调栈
    class Solution {
        private void push(Deque<Integer> stack, int num) {
            while (!stack.isEmpty() && num > stack.getLast()) {
                stack.removeLast();
            }
            stack.addLast(num);
        }

        public int[] maxSlidingWindow(int[] nums, int k) {
            int n = nums.length;
            int[] res = new int[n - k + 1];
            Deque<Integer> stack = new LinkedList<>();
            for (int i = 0; i < k - 1; i++) {
                push(stack, nums[i]);
            }
            for (int i = k - 1; i < n; i++) {
                push(stack, nums[i]);
                res[i - k + 1] = stack.getFirst();
                if (stack.getFirst() == nums[i - k + 1]) {
                    stack.removeFirst();
                }
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}